package colony;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import colony.main.Main;

public class Grid {

	private List<Item> items;
	private int[][] occupied;

	// private Set<Integer> freeItems;
	private List<Integer> freeItems;
	private int count;

	private DistanceMatrix distance;

	private int l;
	private int lastX = -1;
	private int lastY = -1;

	private boolean q1, q2, q3, q4;

	public Grid(List<Item> items, DistanceMatrix distance) {

		this.items = items;
		this.l = Engine.gridSize;
		this.distance = distance;

		occupied = new int[l][l];

		freeItems = new ArrayList<Integer>();
		for (int i = 0; i < items.size(); i++) {
			freeItems.add(items.get(i).getId());
		}

		for (int i = 0; i < l; i++) {
			for (int j = 0; j < l; j++) {
				occupied[i][j] = -1;
			}
		}

		scatterItems();
	}

	public void scatterItems() {
		for (int i = 0; i < items.size(); i++) {
			Item item = items.get(i);
			int x;
			int y;
			do {
				x = Engine.rand.nextInt(l);
				y = Engine.rand.nextInt(l);
			} while (occupied[x][y] != -1);

			occupied[x][y] = item.getId();
			item.setPosition(x, y);
		}
	}

	public boolean isFree(Position pos) {
		return occupied[pos.x][pos.y] == -1;
	}

	public Position nexFree(Position original, Position pos) {

		int radius = 0;
		while (true) {
			radius++;
			int xhigh = pos.x + radius;
			if (xhigh >= this.l) {
				xhigh = this.l - 1;
			}

			int xlow = pos.x - radius;
			if (xlow <= 0) {
				xlow = 0;
			}

			int yhigh = pos.y + radius;
			if (yhigh >= this.l) {
				yhigh = this.l - 1;
			}

			int ylow = pos.y - radius;
			if (ylow <= 0) {
				ylow = 0;
			}
			int count = 0;
			while (count != (xhigh - xlow) * (yhigh - ylow)) {
				int x = xlow + Engine.rand.nextInt(xhigh - xlow);
				int y = ylow + Engine.rand.nextInt(yhigh - ylow);

				if (occupied[x][y] == -1 && x != pos.x && y != pos.y) {
					Position position = new Position();
					position.x = x;
					position.y = y;
					return position;
				}
				count++;
			}

			// for (int x = xlow; x <= xhigh; x++) {
			// for (int y = ylow; y <= yhigh; y++) {
			// if (occupied[x][y] == -1 && x != pos.x && y != pos.y) {
			// Position position = new Position();
			// position.x = x;
			// position.y = y;
			// return position;
			// }
			// }
			// }
		}
	}

	public Position BestPosition(int itemId, Position pos) {

		int xhigh = pos.x + Engine.neighborhoodSize;
		if (xhigh >= this.l) {
			xhigh = this.l - 1;
		}

		int xlow = pos.x - Engine.neighborhoodSize;
		if (xlow <= 0) {
			xlow = 0;
		}

		int yhigh = pos.y + Engine.neighborhoodSize;
		if (yhigh >= this.l) {
			yhigh = this.l - 1;
		}

		int ylow = pos.y - Engine.neighborhoodSize;
		if (ylow <= 0) {
			ylow = 0;
		}

		double best = DistanceMatrix.max + 100;
		int bestX = -1;
		int bestY = -1;
		for (int x = xlow; x <= xhigh; x++) {
			for (int y = ylow; y <= yhigh; y++) {
				if (occupied[x][y] != -1 && (x != pos.x && y != pos.y)) {
					if (distance.get(itemId, occupied[x][y]) < best) {
						bestX = x;
						bestY = y;
					}
					// count++;
				}
			}
		}

		if (bestX == -1) {
			int x, y;
			do {
				x = Engine.rand.nextInt(this.l);
				y = Engine.rand.nextInt(this.l);
			} while (occupied[x][y] != -1 || (x == pos.x && y == pos.y));

			return new Position(x, y);
		} else {
			return nexFree(pos, new Position(bestX, bestY));
		} 
	}

	public Position nextRandom(Position pos, int itemId) {

		boolean hit = false;
		if (pos.x < this.l / 2) {
			if (pos.y < this.l / 2) {
				if (!q1) {
					lastX = (int) Math.round(0.25 * this.l);
					lastY = (int) Math.round(0.25 * this.l);
					q1 = true;
					hit = true;
				}
			} else {
				if (!q2) {
					lastX = (int) Math.round(0.25 * this.l);
					lastY = (int) Math.round(0.75 * this.l);
					q2 = true;
					hit = true;
				}
			}
		} else {
			if (pos.y < this.l / 2) {
				if (!q3) {
					lastX = (int) Math.round(0.75 * this.l);
					lastY = (int) Math.round(0.25 * this.l);
					q3 = true;
					hit = true;
				}
			} else { 
				if (!q4) {
					lastX =  (int) Math.round(0.75 * this.l);
					lastY =  (int) Math.round(0.75 * this.l);
					q4 = true;
					hit = true;
				}
			}
		}

		if (!hit) {

			if (lastX == -1) {
				lastX = pos.x;
			}
			if (lastY == -1) {
				lastY = pos.y;
			}
			double rate;

			do {
				//System.out.println("random");
				lastX = lastX
						+ (int) Math.round(Engine.rand.nextInt(2 * this.l));
				lastY = lastY
						+ (int) Math.round(Engine.rand.nextInt(2 * this.l));
				lastX = getMod(lastX);
				lastY = getMod(lastY);

				Position npos = new Position(lastX, lastY);

				rate = getDstanceAt(itemId, npos);
				// rate = density
				// / (Math.pow(2 * Engine.neighborhoodSize + 1, 2) *
				// Engine.penalty);

			} while ((lastX == pos.x && lastY == pos.y) || (rate < 0.90));
		}

		if (occupied[lastX][lastY] != -1) {
			return nexFree(new Position(lastX, lastY), new Position(lastX,
					lastY));
		}
		return new Position(lastX, lastY);
	}

	public Position moveAnt(Position pos) {
		int x = Engine.rand.nextInt(l);
		int y = Engine.rand.nextInt(l);

		x = x % l;
		y = y % l;

		return new Position(x, y);
	}

	public void freeItem(Item item) {
		freeItems.remove(item.getId());
	}

	public void remove(Position pos) {
		occupied[pos.x][pos.y] = -1;
	}

	public void setItem(Position pos, Item item) {
		occupied[pos.x][pos.y] = item.getId();
	}

	public Item getItemAt(Position pos) {
		int itemId = occupied[pos.x][pos.y];
		freeItems.remove(new Integer(itemId));
		return getItemById(itemId);
	}

	public Item getFreeItem() {
		count = 0;
		if (freeItems.size() > 0) {
			count++;
			if (count % 2 == 0) {
				if (freeItems.size() == 1) {
					int id = freeItems.remove(0);
					Item item = getItemById(id);
					return item;
				}

				int randomNum = Engine.rand.nextInt(freeItems.size() / 2);
//				System.out.println("size: " + freeItems.size() + "\t rand: "
//						+ randomNum);

				int id = freeItems.remove(randomNum);

				Item item = getItemById(id);
				// occupied[item.getPosition().x][item.getPosition().y] = -1;
				return item;
			} else {
				if (freeItems.size() == 1) {
					int id = freeItems.remove(0);
					Item item = getItemById(id);
					return item;
				}

				int randomNum = freeItems.size() / 2
						+ (Engine.rand.nextInt(freeItems.size() / 2));

//				System.out.println("size: " + freeItems.size() + "\t rand: "
//						+ randomNum);

				int id = freeItems.remove(randomNum);

				Item item = getItemById(id);
				// occupied[item.getPosition().x][item.getPosition().y] = -1;
				return item;
			}

		} else {
			return null;
		}
	}

	public void setFreeItem(Item item) {
		occupied[item.getPosition().x][item.getPosition().y] = item.getId();
		freeItems.add(item.getId());
	}

	public Item getItemById(int id) {
		for (Item i : items) {
			if (i.getId() == id) {
				return i;
			}
		}
		return null;
	}

	public double getDstanceAt(int itemId, Position pos) {

		int xhigh = pos.x + Engine.neighborhoodSize;
		if (xhigh >= this.l) {
			xhigh = this.l - 1;
		}

		int xlow = pos.x - Engine.neighborhoodSize;
		if (xlow <= 0) {
			xlow = 0;
		}

		int yhigh = pos.y + Engine.neighborhoodSize;
		if (yhigh >= this.l) {
			yhigh = this.l - 1;
		}

		int ylow = pos.y - Engine.neighborhoodSize;
		if (ylow <= 0) {
			ylow = 0;
		}

		int count = 0;
		double sum = 0;
		for (int x = xlow; x <= xhigh; x++) {
			for (int y = ylow; y <= yhigh; y++) {
				if (occupied[x][y] != -1 && (x != pos.x && y != pos.y)) {
					sum += distance.get(itemId, occupied[x][y]);
					count++;
				} else {
					if (occupied[x][y] == -1) {
						sum += Engine.penalty;
						count++;
					}
				}
			}
		}
		double value = sum / (count * Engine.penalty);
		return value;
	}

	public void print() {
		for (int i = 0; i < occupied.length; i++) {
			for (int j = 0; j < occupied[i].length; j++) {
				if (occupied[i][j] == -1) {
					System.out.print(0);
				} else {
					getItemById(occupied[i][j]).print();
				}
				System.out.print(" ");
			}
			System.out.println();
		}
	}

	private int getMod(int x) {
		int r = x % this.l;
		if (r < 0) {
			r += this.l;
		}
		return r;
	}
}
